package binary_tree;

import java.util.NoSuchElementException;

public class BST {
    //节点个数
    private int size;
    //根节点
    private Node root;
    //节点定义
    private class Node{
        private  int val;
        private Node left;
        private Node right;
        public Node(int val) {
            this.val = val;
        }
    }
    //向BST中插入一个元素
    public void add(int value){
        root=add(root,value);
    }
    private Node add(Node root, int value) {
        //当为空时，直接在根节点处添加元素
        if(root==null){
          root=new Node(value);
          size++;
          return root;
        }
        //当此时添加的值小于根节点时，在左树添加，大于时在右树添加。
        if(root.val>value){
            root.left=add(root.left,value);
            return root;
        }else{
            root.right=add(root.right,value);
            return root;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        generateBSTString(root,0,sb);
        return sb.toString();
    }
    //先序遍历BST
    private void generateBSTString(Node root, int depth, StringBuilder sb) {
        if(root==null){
            sb.append(generateBSTDepth(depth)).append("NULL\n");
            return;
        }
        //先根节点
        sb.append(generateBSTDepth(depth)).append(root.val).append("\n");
        //左子树
        generateBSTString(root.left,depth+1,sb);
        //右子树
        generateBSTString(root.right,depth+1,sb);
    }
    //在BST中查找指定的值
    public boolean contains(int value) {
        return contains(root, value);
    }
    private boolean contains(Node root, int value) {
        if(root==null){
            return false;
            //先找根节点
        }else if(root.val==value){
            return true;
            //找左树
        }else if(root.val>value){
            return contains(root.left,value);
        }
        //找右树
        return contains(root.right,value);
    }
    //查找BST中最大的元素
    public int maxNum(){
       if(size==0){
           throw new NoSuchElementException("BST is empty!");
       }
       Node maxNode=maxNum(root);
       return maxNode.val;
    }

    private Node maxNum(Node root) {
        if(root.right==null){
            return root;
        }
        return maxNum(root.right);
    }
    public int minNum(){
        if(size==0){
            throw  new NoSuchElementException("BST is empty!");
        }
        Node minNode =minNum(root);
        return minNode.val;
    }
   //删除最小值
    private Node minNum(Node root) {
        if(root.left==null){
            return root;
        }
        return minNum(root.left);
    }
    public int removeMin(){
        int min=minNum();
        root=removeMin(root);
        return min;
    }
    private Node removeMin(Node root) {
        if(root.left==null){
            Node right=root.right;
            root.right=null;
            size--;
            return right;
        }
        root.left=removeMin(root.left);
        return root;
    }
    //删除最大值
    public int removeMax(){
        int max=maxNum();
        root=removeMax(root);
        return max;
    }

    private Node removeMax(Node root) {
        if(root.right==null){
            Node left=root.left;
            root.left=null;
            size--;
            return left;
        }
        root.right=removeMax(root.right);
        return root;
    }
    //删除任意位置的元素
    public void remove(int val){
       root= remove(root,val);
    }

    private Node remove(Node root, int val) {
        //此时bst没有元素
        if(root==null){
            return null;
            //此时在左树删除
        }else if(val<root.val){
            root.left=remove(root.left,val);
            return root;
            //此时在右树删除
        }else if(val>root.val){
            root.right=remove(root.right,val);
            return root;
        }else{
            //此时root就是待删除的节点
            if(root.right==null){
                //只有左孩子在左孩子中寻找即可
                Node left=root.left;
                root.left=null;
                size--;
                return left;
            }if(root.left==null){
                //只有右孩子，在右孩子中寻找即可
                Node right=root.right;
                root.right=null;
                size--;
                return right;
            }
            //此时左右两边孩子两边都有
            //找到root的后继节点,找到以root为根节点的右子树中最小值作为后继节点
            Node successor=minNum(root.right);
            //在右孩子中删除最小数，连接为successor的右子树
            successor.right=removeMin(root.right);
            successor.left=root.left;
            root.left=root.right=null;
            return successor;
        }
    }


    //打印当前的BST的深度每增加一层就打印一个"--"
    private String generateBSTDepth(int depth) {
       StringBuilder sb=new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }


}
